//
//  Problem42.swift
//  TestProject 42. 接雨水
//
//  Created by 武侠 on 2020/8/27.
//  Copyright © 2020 zhulong. All rights reserved.
//

import UIKit

/*
 42. 接雨水
 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

 上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

 示例:
 输入: [0,1,0,2,1,0,1,3,2,1,2,1]
 输出: 6
 */
@objcMembers class Problem42: NSObject {
    func solution() {
//        print(trap([0,1,0,2,1,0,1,3,2,1,2,1]))
//        print(trap([8,5,4,1,8,9,3,0,0]))
//        print(trapBaoLi([0,1,0,2,1,0,1,3,2,1,2,1]))
        print(trapBaoLi([8,5,4,1,8,9,3,0,0]))
    }
    
    // 思路：
    // 从左边开始：找到一个凹地，然后得到雨水数，然后继续往后找凹地
    func trap(_ height: [Int]) -> Int {
        // 0 1 2 都不存在雨水
        if height.count <= 2 {
            return 0
        }
        var list = height
        var j = -1
        
        // 过滤掉最开始的0
        for i in 0..<list.count {
            if list[i] != 0 {
                j = i
                break
            }
        }
        if j == -1 {        // 说明数组都是0
            return 0
        }

        var start = list[j]
        var sIndex = j
        var sum = 0
        var sendHeight = 0
        for i in j+1..<list.count {
            if list[i] >= start {   // 找到了一个洼地
                sum += waRain(list, sIndex, i)
                sIndex = i
                start = list[i]
            } else {
                if list[i] > sendHeight {
                    sendHeight = list[i]
                }
            }
        }
        
        // 特殊情况：最左边是最高的边：削平，然后递归
        if sIndex != list.count-1 {
            list[sIndex] = sendHeight
            sum += trap(Array(list[sIndex...list.count-1]))
        }
        return sum
    }
    
    func waRain(_ height:[Int], _ start: Int, _ end: Int) -> Int {
        var sum = 0
        let lowValue = height[start]
        for i in start+1..<end+1 {
            if lowValue >= height[i] {
                sum += lowValue - height[i]
            }
        }
        return sum
    }
    
    // 暴力法：
    // 从[1..count-1], 找到 i:所在凹地的左边最高点和右边最高点，然后min - height[i]，
    func trapBaoLi(_ height:[Int]) -> Int {
        if height.count <= 2 {
            return 0
        }
        
        var sum = 0
        // 1: 先保存，每个位置的左边最大值
        var leftMaxs:[Int] = [height[0]]
        for i in 1..<height.count {
            if leftMaxs[i-1] > height[i] {
                leftMaxs.append(leftMaxs[i-1])
            } else {
                leftMaxs.append(height[i])
            }
        }
        print("左边最大数组：", leftMaxs)
        // 1: 先保存，每个位置的右边最大值
        var rightMaxs:[Int] = [height[height.count-1]]
        var i = height.count - 2
        while i >= 0 {
            if rightMaxs[0] > height[i] {
                rightMaxs.insert(rightMaxs[0], at: 0)
            } else {
                rightMaxs.insert(height[i], at: 0)
            }
            i -= 1
        }
        print("右边最大数组：", rightMaxs)
        
        for i in 1..<height.count-1 {
            
            if leftMaxs[i] < rightMaxs[i] {
                sum += leftMaxs[i] - height[i]
            } else {
                sum += rightMaxs[i] - height[i]
            }
            print(i, sum)
        }
        
        return sum
    }
}
